
\chapter{A infraestrutura de compiladores LLVM}
\label{c:llvm}

O projeto LLVM, inicialmente denominado de \emph{Low Level Virtual Machine},
consiste de uma coleção modular de componentes reutilizáveis para implementação
de compiladores e de ferramentas para análise e otimização de código executável
\cite{llvm_site}. Ele iniciou-se como um projeto de pesquisa na University of
Illinois e hoje em dia conta com um número bastante significativo de
contribuintes internacionais e de sub-projetos criados em topo destes
componentes. É um destaque dentre os exemplos de casos de sucesso em termos de
pesquisa acadêmica na área de compiladores, e uma referência entre as
ferramentas de compilação tanto de código aberto como proprietárias.

\citeonline{llvm_main_art} destacam a principal motivação para a construção
deste projeto como sendo um esforço coletivo para gerenciar a complexidade
inerente na construção de compiladores no estado-da-arte atual. As aplicações
modernas necessitam de tecnologias de compilação que excedam o modelo
tradicional do compilador estático, que realiza análises e otimizações sob o
código fonte original e simplesmente gera o executável final. Um \emph{sistema
de compilação} moderno deve apresentar as seguintes características
\cite{llvm_main_art}:

\begin{itemize}
  \item O gerador de código deve ser capaz de realizar análises complexas no
  código fonte de modo a entender as dependências entre os seus componentes e
  poder realizar otimizações além das barreiras das unidades de compilação.
  
  \item É preciso um conjunto de ferramentas que permitam a otimização de um
  programa ao longo do seu ciclo de vida, e não somente em tempo de compilação.
  
  \item O sistema deve ser capaz de realizar otimizações dinâmicas em tempo de
  execução, utilizando informações obtidas com o comportamento observado do
  software em uma de suas execuções.
  
  \item O sistema deve prover ferramentas para análise estática do código, 
  capazes de extrair informações interessantes sobre o programa. Por exemplo: 
  correção automática de bugs, detecção de vazamentos de memória, etc.
\end{itemize}

Os componentes (módulos) do LLVM participam de todos os passos de análise de
código ao longo do processo de desenvolvimento, provendo ferramentas de código
aberto que podem ser utilizadas e estendidas livremente. Os componentes do LLVM
não são voltados somente para a construção de compiladores estáticos. O projeto
dá suporte a construção de \cite{llvm_tutorial}: interpretadores com
geração de código em tempo de execução (também conhecidos como compiladores
\emph{just in time} (JIT)), ferramentas de monitoramento de dados em tempo de
execução (\emph{profiling}), máquinas virtuais, ferramentas de análise estática,
etc. Cada um dos projetos que utilizam os módulos de baixo nível do LLVM são
independentes da arquitetura alvo, e suportam diversas plataformas diferentes.
Algumas delas são: x86, x86-64, SparcV8, PowerPC, ARM, MSP430 e MIPS.

Para os usuários finais das ferramentas derivadas deste projeto, o LLVM é mais
conhecido pelo seu compilador oficial de C e C++\footnote{A ferramenta Clang
também dá suporte à geração de código para as linguagens Object-C e Object-C++},
o Clang \cite{clang}. A ferramenta Clang utiliza extensivamente a infraestrutura
de geração de código do LLVM para criar um compilador completo, com qualidade
de produção. Além de estar sobre a bandeira do LLVM, há uma relação simbiótica
entre os dois projetos. A construção de um compilador com o porte do Clang fez
com que diversos avanços ocorressem nas bibliotecas do LLVM. Ao mesmo tempo, o
Clang atua como o produto ``oficial'' do projeto, promovendo o seu uso.

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.76]{images/llvm-publicacoes}
  \textsf{\caption[Quantidade anual de trabalhos publicados que utilizam ou
          desenvolvem em topo do projeto LLVM.]
          {Quantidade anual de trabalhos publicados que utilizam ou         
           desenvolvem em topo do projeto LLVM. \emph{Retirado da página
           \cite{llvm_site}} \label{fig:llvm_papers}}}
\end{figure}

Atualmente, projetistas de compiladores e pesquisadores na academia
utilizam o LLVM como uma plataforma robusta para implementar novas ideias e
técnicas da área. A boa qualidade do projeto, aliado a grande base de
contribuidores e usuários e a sua documentação extensiva ajudam a reduzir o
tempo necessário para o desenvolvimento das ferramentas. Além disso, não é
prático para um pesquisador construir um compilador completo, ou tentar
modificar um compilador existente que não tenha uma boa documentação, para que
se possa desenvolver um trabalho. Com o LLVM, é possível utilizar somente os
módulos necessários, bem documentados, diminuindo o esforço. Os dados na figura
\ref{fig:llvm_papers} comprovam estes argumentos para a popularidade do
projeto. 

No início deste trabalho foram analisadas outras alternativas, com o objetivo de
poder criar um compilador de C e C++ para a plataforma RISCO. Foi considerada a
utilização da coleção de compiladores de código aberto GCC \cite{gcc_site},
portando o seu módulo de geração de código para o RISCO. O GCC é o sistema de
compilação oficial em virtualmente todos os sistemas operacionais baseados no
GNU/Linux. Apesar de ser conhecido tradicionalmente pelos seus compiladores C e
C++, a coleção é bastante vasta e o seu código visa a portabilidade para
diversas arquiteturas diferentes\footnote{De fato, ele foi portado para mais
arquiteturas diferentes do que qualquer outro compilador em uso
\cite{gcc_site}}. A principal desvantagem na utilização do GCC para a
implementação de um novo alvo de geração de código é que o seu código é bastante
maduro e otimizado, de difícil legibilidade para desenvolvedores externos ao
projeto. Em outras palavras, a curva de aprendizado necessário para realizar uma
contribuição a este projeto, como é comum aos projetos GNU, é bastante
significativa. Por estes motivos optou-se por utilizar o projeto LLVM para este
trabalho.


\section{Arquitetura}
\label{s:llvm_arquitetura}

O processo de compilação de código com as ferramentas do projeto LLVM é
representado pela figura \ref{fig:llvm_arquitetura}, adaptada de
\cite{llvm_wcet}.

\begin{figure}[thb]
  \centering
  \includegraphics[scale=0.65]{images/llvm-arquitetura}
  \textsf{\caption{Arquitetura das ferramentas do projeto LLVM 
          \label{fig:llvm_arquitetura}}}
\end{figure}

\abrv[RI -- Representação Intermediária]

O software é desenvolvido em uma linguagem de alto nível e depois é compilado,
com um compilador estático tradicional como o Clang, para uma linguagem de
representação intermediária (RI), a \emph{LLVM-IR}. Esta representação
do código é universal entre as ferramentas do LLVM. Em outro passo, um
otimizador em tempo de ligação pode unir o código desenvolvido com bibliotecas
na LLVM-IR ou em código nativo, descobrindo as dependências entre as unidades
para obter mais informações que guiem as otimizações. O executável gerado,
junto com a sua RI equivalente, é produzido. 

Com este código, existem duas opções de otimização em tempo de execução
\cite{llvm_tutorial}. É possível interpretar a sua RI em uma máquina virtual
com compilação em tempo de execução. Ela executa o código interpretado, recebe
informações sobre o seu comportamento, e tenta compilar trechos da IR para
código nativo da plataforma. A outra opção é executar o código binário
normalmente, e utilizar as informações de uma execução em particular para guiar
um otimizador em tempo de compilação, capaz de melhorar a eficiência do código
original. O foco deste trabalho é nos módulos de compilação estática do LLVM.
Não é dado suporte às otimizações em tempo de execução mencionadas.


\section{Representação Intermediária}
\label{s:llvm_ir}

Como visto na seção anterior, todas as ferramentas do projeto LLVM trabalham
com uma representação do código original em uma linguagem intermediária
denominada de \emph{LLVM-IR}. Em particular, o módulo de geração de código do
LLVM recebe como entrada um programa nesta representação. O objetivo da LLVM-IR
é \cite{llvm_llva}: ser um alvo fácil de geração de código; ser independente
da linguagem fonte ou da linguagem alvo; suportar diversos tipos de análises e
transformações eficientemente. Nos componentes do LLVM, o código na RI aparece
em 3 modos diferentes: representação em memória, representação binária para
armazenamento externo e uma representação textual para manipulação manual.

A LLVM-IR é uma representação com estilo de linguagem de montagem, não contêm
construções complexas de fluxo, somente saltos. Ela é próxima de uma linguagem
de montagem, porém suficientemente ``alto nível'' para que o conjunto de
análises e otimizações tradicionais presentes na literatura possam ser
implementados sem dificuldade \cite{llvm_thesis}. A linguagem utiliza instruções
de 3 endereços, semelhante a uma arquitetura RISC. Entretanto, contêm instruções
de mais alto nível, para que possa implementar funcionalidades mais
específicas.

\abrv[SSA -- Static Single Assignment]

Ao contrário de variáveis normais, esta linguagem utiliza um conjunto infinito
de registradores virtuais que só podem ser declarados e definidos uma única vez.
Cada instrução que realiza uma operação gera um outro valor e nunca modifica os
seus operandos. Esta representação, denominada de \emph{Single Static
Assignment} (SSA), é bastante comum \cite{dragon_book, compilers_appel}.
\citeonline{dragon_book} define a SSA como sendo uma forma de representação
intermediária onde todas as atribuições são para nomes diferentes. O uso do SSA
facilita o desenvolvimento de análises do fluxo de dados do programa.

\begin{figure}[ht]
  \centering              
  \subfloat[Exemplo 1]
  {\includegraphics[scale=0.8]{images/ssa-exemplo1}}
  \subfloat[Exemplo 2]
  {\includegraphics[scale=0.8]{images/ssa-exemplo2}}
  \caption{Exemplo de tradução de código de 3 endereços para a forma SSA.}
  \label{fig:exemplos_ssa}
\end{figure}

\simb[$\phi$ -- função Phi, utilizada em códigos na forma SSA]

Considere os exemplos da figura \ref{fig:exemplos_ssa}. No primeiro caso, a
conversão entre as duas representações é direta. No segundo exemplo, não é
possível determinar qual será o valor origem de \texttt{y} pois \texttt{var}
pode ser definida em dois \emph{blocos básicos}\footnote{Bloco básico é um
trecho de código que tem um único ponto de entrada e um único ponto de saída.
Isto é, somente a primeira instrução do bloco pode ser o destino de um salto, e
somente a sua última instrução pode ser um salto. Podem haver chamadas de
subrotinas dentro do bloco.} diferentes. As representações SSA lidam com este
caso utilizando uma função especial, representada por $\phi$. Para o exemplo
2, a última linha seria: \texttt{y1 = $\phi$(var2, var3)}. Esta é uma instrução
fictícia, que retorna um valor dentre todos os possíveis valores de uma
variável, dependendo do fluxo tomado no programa \cite{compilers_appel}. Ela é
eliminada no passo de geração de código.

A LLVM-IR é uma linguagem tipada, com construções de tipos compostos e
operadores de conversão (\emph{cast}) entre tipos. Suporta inteiros, boleanos,
números em ponto flutuante, arranjos, vetores (de tamanho fixo), estruturas
compostas e ponteiros \cite{llvm_thesis}. Apresentamos a seguir um resumo da
estrutura dos programas nesta linguagem, como definido em \cite{llvm_site}. É
necessário se familiarizar com a LLVM-IR para entender o funcionamento do módulo
\texttt{risco-llvm}.

Um programa LLVM é definido como um \emph{Módulo} e equivale a uma unidade de
compilação. Cada módulo é composto por: funções, variáveis globais e
declarações de símbolos. Os módulos podem ser combinados com o ligador do LLVM
(\texttt{llvm-ld}), que realiza otimizações em tempo de ligação. Uma função é
uma lista de blocos básicos, cada um iniciado com um rótulo. Um bloco básico é
uma lista de instruções, seguindo as restrições apresentadas anteriormente.
Todos os valores na linguagem são tipados. Os tipos podem ser classificados em
4 classes: inteiros (um tipo para cada quantidade de bits no inteiro), ponto
flutuante, primitivos (rótulos, \texttt{void}) e derivados (arranjos, funções,
ponteiros, etc.). As instruções podem ser classificadas em:

\abrv[SIMD -- Single Instruction, Multiple Data]

\begin{itemize}
  \item \emph{Instruções de término}: São as instruções que devem aparecer no
  final de um bloco básico, manipulando o fluxo de controle no programa. Fazem
  parte destas: \texttt{ret} (retorno de subrotina), \texttt{br} (salto
  direto, opcionalmente condicional), \texttt{indirectbr} (salto com
  endereçamento indireto) e \texttt{invoke} (chamada de rotina).
  
  \item \emph{Operações binárias}: realizam as operações aritméticas e lógicas
  do programa. Cada instrução tem dois operandos do mesmo tipo e produz um
  único valor. Exemplos deste tipo são: \texttt{add}, \texttt{sub},
  \texttt{mul}, \texttt{udiv} e \texttt{shl} (deslocamento para esquerda).
  
  \item \emph{Operações vetoriais}: trabalham com operandos que representam um
  vetor de valores, úteis para arquiteturas SIMD. Existem operações para
  extrair e modificar elementos do vetor, por exemplo.
  
  \item \emph{Operações de conversão}: convertem um valor de um tipo para outro
  tipo. Inclui operações de truncamento (\texttt{trunc..to}) e extensão com
  ou sem sinal (\texttt{zext..to} e \texttt{sext..to}).
  
  \item \emph{Instruções de acesso a memória}: as posições de memória fogem da
  representação SSA utilizada para os valores primitivos e são manipuladas com
  instruções \texttt{load} e \texttt{store}, que recebem ponteiros como 
  argumentos. Existe uma instrução especial para alocar um valor na pilha
  (\texttt{alloca}).
  
  \item \emph{Instrução \texttt{phi}}: tem o significado da função $\phi$
  discutida anteriormente.
\end{itemize}

\begin{figure}
  \begin{subfigure}[b]{.5\linewidth}
    \begin{verbatim}
    int f(int* n) {
      return *n + 1;
    }
    
    int main(void) {
      int x;
      x = 4;
      return f(&x);
    }
    
   
    \end{verbatim}
    \caption{C}
  \end{subfigure}
  \begin{subfigure}[b]{.5\linewidth}
    \begin{verbatim}
   int %f(int* %n) {
    entry:
     %tmp.1 = load int* %X
     %tmp.2 = add int %tmp.1, 1
     ret int %tmp.2
   }
   int %main() {
    entry:
     %x = alloca int
     store int 4, int* %x
     %tmp.3 = call int %f(int* %x)
     ret int %tmp.3
   }
    \end{verbatim}
  \caption{IR}
  \end{subfigure}
  \caption{Exemplo de tradução de um programa C para a LLVM-IR}
  \label{fig:exemplo_c_ir}
\end{figure}

A figura \ref{fig:exemplo_c_ir} mostra um exemplo de tradução de um código C
para a representação intermediária do LLVM. Note a utilização da forma SSA e
das instruções de 3 endereços. A LLVM-IR tem as construções baixo nível
necessárias para representar as operações com detalhes e, ao mesmo tempo,
mantêm informações de tipos de ponteiros, necessárias para as otimizações mais
agressivas \cite{llvm_llva}. 


\section{Framework para geração de código}
\label{s:llvm_codegen}

O módulo de geração de código do LLVM consiste de um conjunto de componentes
reutilizáveis responsáveis pela tradução de código na representação
intermediária para o código de máquina da arquitetura alvo em forma de linguagem
de montagem ou diretamente para o código binário executável. A segunda forma
está relacionada com a implementação das otimizações em tempo de execução do
LLVM, discutidas em \ref{s:llvm_arquitetura}, e está fora do escopo do
trabalho. Será analisada somente a geração de código em linguagem de montagem.

O framework em si é escrito em C++ e, como o compilador Clang, é implementado
como uma série de \emph{passes} de análise e transformação, responsáveis por
gradualmente produzir o código de máquina final. A geração de código ocorre
após todos os passes de otimização na linguagem intermediária terem sido
executados. Todos os seus componentes são facilmente substituíveis, incluindo o
alocador de registradores (existem 4 opções disponíveis), o seletor de
instruções e o escalonador de instruções. Existem 4 tipos de componentes no
gerador que são relevantes para o RISCO \cite{llvm_backend}:

\begin{itemize}
  \item Um conjunto de interfaces abstratas que especificam propriedades da
  arquitetura alvo e são implementadas por cada módulo dos alvos suportados
  pelo LLVM. Para uniformizar as notações utilizadas no texto, todo o código
  específico a um alvo será referido como sendo um dos ``backends'' do LLVM.
  
  \item Classes que modelam o código de máquina em si, independentemente da
  arquitetura alvo. Por exemplo: instruções, funções e registradores.
  
  \item Algoritmos independentes do alvo, implementados como passes nas
  representações intermediárias do gerador de código. Aqui pertencem os
  algoritmos de alocação de registradores, por exemplo.
  
  \item Os diversos backends pertencentes ao projeto LLVM. São os aglomerados
  de classes e descrições que dão suporte a uma determinada arquitetura alvo,
  distribuídos como bibliotecas dinâmicas \cite{linkers_loaders}. O
\texttt{risco-llvm} é um dos backends do LLVM.
\end{itemize}

O processo de geração de código em si é dividido em 7 passos \cite{llvm_site},
mencionados abaixo. Além destes, um backend em particular pode adicionar mais
passos no processo, para algum requisito específico. Esta técnica é utilizada
pelo backend RISCO.

\begin{enumerate}
  \item \textbf{Seleção de instruções}: Descobre como representar as instruções
  da LLVM-IR utilizando as instruções da arquitetura alvo. Transforma o código
  original em um grafo de instruções da máquina.
  
  \item \textbf{Escalonamento de instruções}: Tendo como entrada o grafo de
  instruções de máquina, esta etapa determina uma ordenação das instruções que
  atenda as restrições da plataforma alvo. O código é emitido na forma SSA
  (infinitos registradores).
  
  \item \textbf{Otimizações na forma SSA}: É uma etapa opcional com otimizações
  específicas ao alvo, comumente denominadas de otimizações \emph{peephole}
  \cite{dragon_book} pois trabalham em pequenos trechos sequenciais do código.
  
  \item \textbf{Alocação de registradores}: É o passo que elimina as
  referências para registradores virtuais, escolhe os registradores físicos
  correspondentes e emite código para realizar leitura e escrita a memória,
  quando necessário.
  
  \item \textbf{Emissão do prólogo e do epílogo}: Após a alocação de
  registradores, o gerador já sabe qual vai ser o tamanho do quadro da função na
  pilha e pode emitir o código de prólogo e epílogo da função.
  
  \item \textbf{Otimizações finais}: É o último passo de otimização e trabalha
  com uma ordenação final das instruções. Serve para eliminar as últimas
  redundâncias que não foram encontradas nos passes de otimização anteriores.
  
  \item \textbf{Emissão do código}: É o passo que de fato emite o código,
  escrevendo o arquivo de texto final utilizando a sintaxe do montador alvo.
\end{enumerate}

Nas seções a seguir, são discutidos em mais detalhes os componentes pertencentes
ao gerador de código que são relevantes para o desenvolvimento de um novo
backend.

\subsection{Descrição do alvo}
\label{ss:llvm_descricao_alvo}

As descrições de todas as características da arquitetura alvo são concentradas
em um conjunto de classes que implementam interfaces abstratas em C++,
definidas no framework LLVM. Os métodos virtuais destas interfaces permitem que
a parte genérica do gerador de código consiga trabalhar com os detalhes de cada
plataforma alvo. A implementação de certas interfaces para cada backend LLVM é
uma tarefa mecânica, envolvendo a definição de muitos métodos que retornam
informações simples ou repetitivas \cite{llvm_mips_arm}. Para introduzir
diversas funcionalidades que facilitam este tipo de tarefa, o projeto LLVM
utiliza uma linguagem de descrição de dados denominada \emph{TableGen}
\cite{llvm_site}.

Uma especificação no formato TableGen consiste de um arquivo contendo descrições
textuais de dois tipos de entidades básicas: registros e classes. Um
registro é um identificador associado a uma lista de atributos e seus
respectivos valores. Uma classe funciona como um template para a construção de
registros, agregando informações que se repetem entre diversos registros. Os
valores podem ser de tipos primitivos, como inteiros, boleanos e strings, como
também de tipos compostos, como grafos completos. Por exemplo: pode-se definir
uma classe \texttt{Instrução}, que tem como parâmetros um inteiro,
correspondente ao seu \texttt{código} e uma string com o seu \texttt{mnemônico}.
Após essa definição, podemos especificar um registro para cada tipo de
instrução, instanciando a classe \texttt{Instrução} com os dados de cada
uma. Existem outras facilidades na ferramenta TableGen que também auxiliam a
reduzir o tamanho das definições das classes de descrição dos alvos. 

As interfaces que devem ser implementadas pelos backends do LLVM permitem a
obtenção de informações diversas sobre o alvo, tais como \cite{llvm_backend}:
layout de memória dos executáveis, alinhamento dos tipos de dados básicos,
tamanhos dos ponteiros; informações sobre os registradores da máquina, seus
identificadores, tamanhos, restrições e sub-registradores; informações sobre as
instruções da plataforma, seus mnemônicos, número e tipo dos operandos, modos
de endereçamento, padrões para seleção de instruções, etc.

\subsection{Seleção de Instruções}
\label{ss:llvm_instruction_selection}

Como já foi mencionado, a etapa de seleção de instruções é responsável por
transformar as instruções da representação intermediária em instruções da
plataforma alvo. A tradução não é realizada a cada instrução, buscando uma
equivalente na plataforma alvo, pois este tipo de seleção gera código bastante
ineficiente \cite{compilers_appel}. O motivo é que nem todas as instruções da
LLVM-IR sempre têm uma contrapartida na plataforma alvo. Mais ainda, em alguns
casos, existem diversas maneiras diferentes de traduzir uma instrução da RI. A
escolha a ser tomada pode depender do contexto em que as instruções serão
inseridas. Como foi visto no capítulo \ref{c:risco}, um dos papéis de um backend
LLVM é disponibilizar um conjunto de padrões de seleção de instruções da RI
para instruções da máquina. O seletor de instruções pode utilizar as informações
deste conjunto para guiar as suas decisões.

\abrv[DAG -- Directed Acyclic Graph]

O seletor de instruções trabalha com uma representação do código na forma de um
\emph{grafo acíclico direcionado}, denominado de \texttt{SelectionDAG} (do
inglês \emph{Directed Acyclic Graph}). O SelectionDAG é uma abstração do código
na representação intermediária. Os nós do grafo são pertencentes a duas
classes: nós de \emph{operação} e nós de \emph{ordenação}. Os primeiros
representam uma operação do código, onde os seus operandos são arestas
direcionadas para os nós que definem os operandos. Note que esta definição segue
diretamente do código, pela sua representação SSA na LLVM-IR. Os nós de
ordenação são nós fictícios inseridos na etapa de construção do grafo que servem
para determinar uma ordenação parcial para os nós do grafo que respeite a ordem
original dos acessos a memória com as instruções \texttt{load} e \texttt{store},
que não obedecem a forma SSA.

\citeonline{dragon_book} demonstra a utilização de uma representação em forma de
DAG para cada expressão de um programa (de modo a identificar sub-expressões em
comum) diferentemente da abordagem utilizada pelo LLVM, onde um bloco básico
inteiro pode ser considerado como um DAG. O processo de seleção de instruções
abordado em \cite{dragon_book} e \cite{compilers_appel} é baseado em
reescrita de árvores, ao contrário de grafos. Ambos abordam um algoritmo
guloso, denominado \emph{maximal munch}, e um algoritmo baseado em programação
dinâmica que consegue determinar a seleção ótima de instruções, baseando-se nos
custos de cada padrão.

\begin{algorithm}[htp]
\caption[Algoritmo guloso para seleção de instruções em forma de árvore]
        {MaximalMunch}
\label{alg:maximal_munch}
\begin{algorithmic}
\REQUIRE \textbf{Node}, o nó raiz da árvore; \textbf{Patterns}, a lista de
padrões da arquitetura alvo
\ENSURE \textbf{Node} é modificado para utilizar as instruções selecionadas.
\STATE

\IF{Node não é uma instrução ou expressão nativa}
\STATE $\text{P} \gets \{ pat \in \text{Patterns} \; | \; \text{casa}(pat,
        \text{Node})\}$
\STATE $\text{pat} \gets \text{o padrão em P com maior número de nós, ignorando
       empates}$
\STATE $\text{reescrever}(\text{node}, \text{pat})$
\ENDIF

\FORALL{$\text{next} \in \text{filhos}(\text{Node})$}
  \STATE $\text{MaximalMunch}(\text{next})$
\ENDFOR
\end{algorithmic}
\end{algorithm}

Em geral, o problema de encontrar a seleção de instruções ótima para grafos
acíclicos direcionados é NP-completo \cite{dag_selection}, ao contrário do que
foi visto para árvores. O algoritmo utilizado pelo LLVM é uma variação do
algoritmo guloso maximal munch, adaptado para trabalhar com o DAG
\cite{llvm_thesis}. O funcionamento básico do algoritmo (para árvores) é
descrito no exemplo \ref{alg:maximal_munch}, adaptado de \cite{compilers_appel}.
\citeonline{dag_selection} apresenta um trabalho de desenvolvimento de um novo
seletor de instruções para o LLVM, capaz de encontrar soluções ``quase
ótimas''. Não é do nosso conhecimento se este seletor já está em uso na versão
oficial do LLVM. O processo de seleção do LLVM, além do algoritmo propriamente
dito, apresenta as seguintes etapas \cite{llvm_site}:

\begin{enumerate}
  \item \emph{Construção do DAG}: a primeira versão do grafo de seleção é
  construída diretamente do código em LLVM-IR. Este grafo é denominado 
  ``ilegal'' pois utiliza instruções e tipos de dados que não são suportados 
  pela plataforma alvo.
  
  \item \emph{Otimizações genéricas (A)}: Um passe que realiza simplificações
  no grafo é executado.
  
  \item \emph{Legalização}: O passe de legalização é responsável por
  transformar o SelectionDAG e eliminar o uso de instruções e tipos de dados não
  pertencentes no alvo. O grafo é reescrito pelo backend.
  
  \item \emph{Otimizações genéricas (B)}: O passe de otimização genérica é
  executado novamente para eliminar as redundâncias que possam vir a ser
  introduzidas pelo processo de legalização do grafo.
  
  \item \emph{Seleção}: Finalmente, o algoritmo de seleção de instruções é
  executado, transformando o SelectionDAG em um grafo em que todos os nós de
  operação utilizam instruções da arquitetura alvo. Esta seleção é  baseada nos
  padrões disponibilizados pelo backend.
  
  \item \emph{Escalonamento}: Este passe decide uma ordenação completa para as
  instruções do grafo de seleção legalizado.
\end{enumerate}

Após este processo, o código já utiliza instruções da plataforma alvo, porém
ainda utiliza registradores virtuais e apresenta redundâncias que serão
eliminadas em passes de otimização posteriores, como já foi descrito.

\subsection{Emissão de código}

Após a alocação de registradores e os últimos passes de otimização no código de
máquina, o gerador de código do LLVM irá emitir um arquivo texto contendo o
código final em linguagem de máquina. Para poder produzir este arquivo, o
gerador consulta uma classe do backend responsável por informar as
características sintáticas da linguagem de montagem. O componente emissor
assume um conjunto mínimo de diretivas e construções para: declarar e definir
dados, instruções, macros, rótulos, etc. A linguagem descrita em
\ref{ss:gramatica_semantica_assembly} atende a estes requisitos.

Nos próximos capítulos será discutido o trabalho que foi desenvolvido utilizando
o projeto LLVM e o seu framework de geração de código, exposto nesta
seção.
